﻿#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Node 
{
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) 
    {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) 
    {
        val = _val;
        children = _children;
    }
};

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    // 429. N 叉树的层序遍历
    vector<vector<int>> levelOrder(Node* root)
    {
        vector<vector<int>> ret;    // 记录最终结果
        queue<Node*> q;             // 辅助层序遍历的队列
        if (root == nullptr)
            return ret;
        q.push(root);

        while (q.size())
        {
            size_t sz = q.size();        // 统计本层元素个数
            vector<int> tmp;        // 统计本层结点
            for (int i = 0; i < sz; i++)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for (auto child : t->children)   // 下一层结点入队列
                {
                    if (child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }

    // 103. 二叉树的锯齿形层序遍历
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        if (root == nullptr)
            return ret;
        q.push(root);
        int level = 1;

        while (q.size())
        {
            size_t sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if (t->left)
                    q.push(t->left);
                if (t->right)
                    q.push(t->right);
            }
            if (level % 2 == 0)
                reverse(tmp.begin(), tmp.end());
            level++;
            ret.push_back(tmp);
        }
        return ret;
    }
};

int main()
{

    return 0;
}